package com.oocl.LinkedList;

import org.junit.runner.manipulation.Sortable;


/**
 * 双向链表
 * 
 * 1 初始化 2 插入 3 删除节点 4 排序 5 二分查找
 * 
 * @author WENGTO2
 * 
 */
public class DoubleLinkedList<T extends Comparable<? super T>> {

	private Node<T> head; // 头节点
	private Node<T> tail;// 尾节点
	private int count; // 链表的长度

	/**
	 * 初始化
	 * 
	 */
	public DoubleLinkedList() {
		this.head = new Node<T>(null);
		this.tail = head;
		this.count = 0;
	}

	public DoubleLinkedList(T data) {
		this.head = new Node<T>(data);
		this.tail = head;
		this.count = 1;
	}

	public DoubleLinkedList(T[] datas) {
		for (T data : datas) {
			this.insert_tail(data);
		}
	}

	/**
	 * 插入
	 */
	public void insert_tail(T data) {
		// 判断是不是为空
		if (this.count == 0) {
			head = new Node<T>(data);
			tail = head;
			count = 1;
		} else {
			Node<T> tmp = new Node<T>(data);
			tmp.setPrev(tail);
			tail.setNext(tmp);
			tail = tmp;
			count++;
		}

	}

	public void insert_head(T data) {
		// 判断是不是为空
		if (this.count == 0) {
			head = new Node<T>(data);
			tail = head;
			count = 1;
		} else {
			Node<T> tmp = new Node<T>(data);
			tmp.setNext(head);
			head.setPrev(tmp);
			head = tmp;
			count++;
		}

	}

	public Node<T> findNode(T data) {
		Node<T> tmp = head;
		if (head != null) {
			while (tmp != null) {
				if (data.equals(tmp.getData())) {
					return tmp;
				}
				tmp = tmp.getNext();
			}
		}
		return null;
	}

	/**
	 * 删除节点
	 * 
	 */
	public void delNode(T data) {

		Node<T> tmp = findNode(data);
		if (tmp != null) {
			if (tmp.getPrev() == null) {
				head = tmp.getNext();
				head.setPrev(null);
			} else if (tmp.getNext() == null) {
				tail = tail.getPrev();
				tail.setNext(null);
			} else {
				tmp.getPrev().setNext(tmp.getNext());
				tmp.getNext().setPrev(tmp.getPrev());
			}

			count--;
		}
	}
	
	
	/**
	 * 排序（ 冒泡）
	 */
	public void sort() {
		
		Node<T> p = head;
		for (int i = 0; i < count-1; i++) {
			p = head;
			for (int j = 0; j < count - i - 1; j++) {
				if (p.getData().compareTo(p.getNext().getData()) > 0) {
					// 进行交换 交换左右两边的数据
//					p.getPrev().setNext(p.getNext());
//					p.getNext().getNext().setPrev(p);
//					p.getNext().setPrev(p.getPrev());
//					p.setPrev(p.getNext());
//					p.setNext(p.getNext().getNext());
//					p.getNext().setNext(p);
					T tmp = p.getData();
					delNode(tmp);
					insert_tail(tmp);
					p = p.getPrev();
				}
				 p = p.getNext();
			}
		}
	}

	/**
	 * 二分查找
	 * 
	 * @param target
	 */
	public boolean binarySearch(T target) {

		int left = 0;
		int right = count - 1;
		int mid = 0;

		while (left <= right) {
			mid = (right + left) / 2;
			if (get(mid).compareTo(target)==0) {
				return true;
			} else if (get(mid).compareTo(target)>0) {
				right = --mid;
			} else {
				left = ++mid;
			}
		}

		return false;
	}

	/**
	 * 
	 * @param index
	 * @return
	 */
	public T get(int index) throws IndexOutOfBoundsException {
		if (index > count || index < 0) {
			throw new IndexOutOfBoundsException("索引越界:" + index);
		}
		Node<T> tmp  = head;
		for (int i = 0; i < index; i++) {
			tmp = tmp.getNext();
		}
		return tmp.getData();
	}
	
	

	
	/**
	 * 输出
	 */
	public void printList() {
		if (this.count == 0) {
			System.out.println("空链表");
		} else {
			sort();
			Node<T> tmp = head;
			for (int i = 0; i < count; i++) {
				System.out.print(tmp.getData() + " ");
				tmp = tmp.getNext();
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		
		Integer[] src ={1,34,3,24,13,15,23,34};
		
		DoubleLinkedList<Integer> list = new DoubleLinkedList<Integer>(src);

//		list.insert_head(1);
//		list.insert_head(2);
//		list.insert_head(3);
//		
//		list.insert_tail(31);
//		list.insert_tail(32);
//		list.insert_tail(33);
	
	
//		list.delNode(1);
		
		list.sort();
		
		System.out.println(list.binarySearch(34));
		
		list.printList();
		

	}

}
